/*
 * @lc app=leetcode.cn id=449 lang=cpp
 *
 * [449] 序列化和反序列化二叉搜索树
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

#include "include.h"

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        std::string data;
        preorderTraverse(root, data);
        inorderTraverse(root, data);
        return data;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        if (data.empty()){return nullptr;}

        TreeNode* res = new TreeNode(data[0]);

        int nodeNum = int(data.size())/4;

        std::vector<int> frontTraverseVec, middleTraverseVec;
        decodeNodeVal(data, frontTraverseVec, nodeNum, 0);
        decodeNodeVal(data, middleTraverseVec, nodeNum, nodeNum*4);

        // rebuild binary tree by front&middle traverse

        // todo

        return res;
    }

    void preorderTraverse(TreeNode* root, std::string& treeSeries){
        if (!root){return;}
        encodeNodeVal(root->val, treeSeries);
        preorderTraverse(root->left, treeSeries);
        preorderTraverse(root->right, treeSeries);
    }

    void inorderTraverse(TreeNode* root, std::string& treeSeries){
        if (!root){return;}
        preorderTraverse(root->left, treeSeries);
        encodeNodeVal(root->val, treeSeries);
        preorderTraverse(root->right, treeSeries);
    }

    void encodeNodeVal(int val, std::string& treeSeries){
        // 16 ^ 4 = 65,536 > 10 ^ 4
        // val > 0 , unsigned
        unsigned char counter = 0;
        while (counter < 4){
            char byte = val % 16;
            val = val / 16;
            treeSeries.push_back(byte);
            counter++;
        }
    }

    void decodeNodeVal(std::string& treeSeries, 
                       std::vector<int>& decodeVec,
                       int nodeNum, int startIndex){
        int nodeVal = 0;
        for (int i=0;i<nodeNum;i++){
            nodeVal = treeSeries[startIndex+i*4+0] +
                      treeSeries[startIndex+i*4+1]*16 +
                      treeSeries[startIndex+i*4+2]*256 +
                      treeSeries[startIndex+i*4+3]*256*16;
            decodeVec.push_back(nodeVal);
        }
    }
};

// Your Codec object will be instantiated and called as such:
// Codec* ser = new Codec();
// Codec* deser = new Codec();
// string tree = ser->serialize(root);
// TreeNode* ans = deser->deserialize(tree);
// return ans;
// @lc code=end

